package basic.study.leetcode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @ClassName Easy283
 * @Description 移动零
 * @Company inspur
 * @Author Kevin
 * @Date 2020/7/11 10:26
 * @Version 1.0
 */
public class Easy283 {
    /**
     * 插入排序变种
     */
    static class Solution {
        public void moveZeroes(int[] nums) {
            if (nums == null || nums.length == 0 || nums.length == 1) {
                return;
            }
            for (int i = 1; i < nums.length; i++) {
                int val = nums[i];
                int j;
                for (j = i-1; j >= 0; j--) {
                    if (nums[j] == 0) {
                        nums[j+1] = nums[j];
                    } else {
                        break;
                    }
                }
                nums[j+1] = val;
            }
        }

        public void swap(int[] nums, int p, int q) {
            int temp = nums[p];
            nums[p] = nums[q];
            nums[q] = temp;
        }
    }
    /**
     * 队列
     */
    static class Solution1 {
        public void moveZeroes(int[] nums) {
            if (nums == null || nums.length == 0 || nums.length == 1) {
                return;
            }

            Queue<Integer> queue = new LinkedList<>();
            for (int i: nums) {
                if (i != 0) {
                    queue.offer(i);
                }
            }
            int qSize = queue.size();
            for (int i = 0; i < qSize; i++) {
                nums[i] = queue.poll();
            }
            for (int i = qSize; i < nums.length; i++) {
                nums[i] = 0;
            }
        }

        public void swap(int[] nums, int p, int q) {
            int temp = nums[p];
            nums[p] = nums[q];
            nums[q] = temp;
        }
    }

    public static void main(String[] args) {
        int[] test  = new int[]{0,1,0,3,12};
        Solution1 solution = new Solution1();
        solution.moveZeroes(test);
        for (int i: test) {
            System.out.println(i);
        }
    }
}
